/**

A group of friends went on holiday and sometimes lent each other money.
For example, Alice paid for Bill's lunch for $10.
Then later Chris gave Alice $5 for a taxi ride.
We can model each transaction as a tuple (x, y, z) which means person x gave person y $z.
Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID),
the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people,
return the minimum number of transactions required to settle the debt.

Note:

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:

Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:

Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.

*/

/**
 * @param {number[][]} transactions
 * @return {number}
 */
const minTransfers = function (transactions) {
  if (transactions.length === 0) return 0
  const map = new Map()
  for (let [a, b, m] of transactions) {
    if (!map.has(a)) map.set(a, 0)
    if (!map.has(b)) map.set(b, 0)
    map.set(a, map.get(a) - m)
    map.set(b, map.get(b) + m)
  }
  const debts = [...map.values()].filter(debt => debt !== 0)
  const len = debts.length
  const dfs = (id, d) => {
    if (id >= d.length) return 0
    const cur = d[id]
    if (cur === 0) return dfs(id + 1, d)

    let res = Infinity
    for (let i = id + 1; i < len; i++) {
      const next = d[i]
      if (cur * next < 0) {
        d[i] = cur + next
        res = Math.min(res, 1 + dfs(id + 1, d))
        d[i] = next
        if (next + cur === 0) break
      }
    }
    return res
  }
  return dfs(0, debts)
}
